package com.zx._12_算法.algorithm.sort.demo;

import com.zx._12_算法.Nums;

public class Demo1 {

    // 冒泡
    public static void main1(String[] args) {
        int[] nums = Nums.nums;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                int n1 = nums[j];
                int n2 = nums[j + 1];
                if (n1 < n2) {
                    nums[j] = n2;
                    nums[j + 1] = n1;
                }
            }
        }
        Nums.print();
    }

    // 选择排序, 从大到小
    public static void main2(String[] args) {
        int[] nums = Nums.nums;
        for (int i = 0; i < nums.length; i++) {
            int maxIndex = i;
            for (int j = i; j < nums.length; j++) {
                if (nums[maxIndex] < nums[j]) {
                    maxIndex = j;
                }
            }

            if (maxIndex != i) {
                int temp = nums[i];
                nums[i] = nums[maxIndex];
                nums[maxIndex] = temp;
            }
        }
        Nums.print();
    }

    // 插入排序, 从大到小
    public static void main3(String[] args) {
        int[] nums = Nums.nums;
        for (int i = 1; i < nums.length; i++) {
            int needNum = nums[i];
            int needIdx = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (needNum < nums[j]) {
                    nums[j + 1] = nums[j];
                } else {
                    needIdx = j + 1;
                    break;
                }
            }
            nums[needIdx] = needNum;
        }
        Nums.print();
    }

    // 希尔排序(最后记一下)
    public static void main4(String[] args) {
        int[] nums = Nums.nums;
        int len = nums.length;
        int gap = len / 2;
        while (gap != 0) {
            for (int i = gap; i < nums.length; i++) {
                int num = nums[i];
                int j = i - gap;

                while (j >= 0 && nums[j] > num) {
                    nums[j + gap] = nums[j];
                    j = j - gap;
                }

                nums[j + gap] = num;
            }
            gap = gap / 2;
        }
        Nums.print();
    }

    // 快速排序(最后记一下)
    // https://www.jianshu.com/p/a68f72278f8f
    public static void main5(String[] args) {
        int[] nums = Nums.nums;
        quickSort(nums, 0, nums.length - 1);
        Nums.print();
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int left = start;
        int right = end;
        while (right > left) {
            // 找到一个基准值
            int base = arr[left];
            //从后向前比较,最多走到right = left+1的位置
            while (right > left && arr[right] >= base) {
                right--;
            }
            // 上面right走到left+1的位置后，继续right--，之后无法进行循环了，所以继续比较right与base
            if (arr[right] <= base) {
                swap(arr, right, left);
            }

            //从前向后比较
            while (right > left && arr[left] <= base) {
                left++;
            }
            if (arr[left] >= base) {
                swap(arr, right, left);
            }
        }
        // start 往左走了，说明start~left是一个分组
        if (left > start) {
            quickSort(arr, start, left - 1);
        }

        if (right < end) {
            quickSort(arr, right + 1, end);
        }
    }

    // 堆排序
    public static void main6(String[] args) {
        int[] nums = Nums.nums;
        sortArray(nums);
        Nums.print();
    }

    public static int[] sortArray(int[] arr) {
        // 1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            // 从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        // 2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);// 将堆顶元素与末尾元素进行交换
            adjustHeap(arr, 0, j);// 重新对堆进行调整
        }
        return arr;
    }

    /**
     * @param arr
     * @param i
     * @param length
     * @Title: 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @date: 2020年3月16日上午10:47:29
     * @author: zhangxue
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = 2 * i + 1;
                k < length;
                k = 2 * k + 1) {
            // 从i结点的左子结点开始，也就是2i+1处开始
            // 如果左子结点小于右子结点，k指向右子结点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            // 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
            arr[i] = temp;//将temp值放到最终的位置
        }


    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
